'''
Created on 2012-8-2

@author: Xindong
'''


from shortcuts import execute_select, log_info
from algorithms import algorithm
import graph_connector
import graph_coupling


def contract_nodes(graph):
    for dep in graph:
        for arr in graph[dep]:
            if dep not in graph[arr]:
                graph[arr][dep] = graph[dep][arr]
    #Firstly we consider the graph as undirected
    contracted_nodes = set([node for node in graph if len(graph[node]) == 2])
    non_contracted_nodes = set([node for node in graph if len(graph[node]) != 2])
    path_list = []
    for node in non_contracted_nodes:
        for t in graph[node]:
            s = node
            path = [(s, t, graph[s][t])]
            while t in contracted_nodes: #len(graph[t].keys()) == 2
                x = [x for x in graph[t] if x != s][0]
                path.append((t, x, graph[t][x]))
                s, t = t, x
            path_list.append(path)
    core_arcs = []
    for path in path_list:
        dep, arr, cost = path[0][0], path[-1][1], sum([c[2] for c in path])
        core_arcs.append((dep, arr, cost))
    return core_arcs


def remove_useless_transfers(adjacency, transfer_arcs, contracted_nodes):
    transfer_arcs_set = {(a, b) for (a, b, _c) in transfer_arcs}
    new_transfer_arcs = []
    for a, b, cost in transfer_arcs:
        if (a in contracted_nodes and b in contracted_nodes):
            [na1, na2] = list(adjacency[a])
            [nb1, nb2] = list(adjacency[b])
            if ((na1, nb1) in transfer_arcs_set and (na2, nb2) in transfer_arcs_set or 
                (na1, nb2) in transfer_arcs_set and (na2, nb1) in transfer_arcs_set):
                continue
        new_transfer_arcs.append((a, b, cost))
    log_info("%d useless transfer arcs removed" % (len(transfer_arcs) - len(new_transfer_arcs)))
    return new_transfer_arcs


def update_graph(graph, arcs):
    for dep, arr, cost in arcs:
        if dep not in graph:
            graph[dep] = dict()
        if arr not in graph:
            graph[arr] = dict()
        graph[dep][arr] = cost


def local_hierarchy(dataset_name):
    ''' First 2 levels' hierarchy on a local graph
            local graph is a single network or several networks covering the same region
        Level 1 hierarchy - Contract bypassed nodes
        Level 2 hierarchy - Find hubs
    '''
    
    log_info("Level 1 graph hierarchy - intra coupling: " + dataset_name)
    adjacency = graph_connector.load_adjacency_matrix(dataset_name)
    transfer_arcs = graph_coupling.intra_graph_transfers(dataset_name, adjacency)
    contracted_nodes = [node for node in adjacency if len(adjacency[node]) == 2]
    transfer_arcs = remove_useless_transfers(adjacency, transfer_arcs, contracted_nodes)
    del adjacency
    
    #TODO: following line is to be removed, its just temporary walking links for test 
    graph_connector.insert_global_arcs(transfer_arcs, 0)
    
    #TODO: now we only do walking links
    return
    
    log_info("Level 1 graph hierarchy - contracting: " + dataset_name)
    graph = graph_connector.load_local_graph(dataset_name)
    update_graph(graph, transfer_arcs)
    core_arcs = contract_nodes(graph)
    del graph
    
    """ update highway graph """
    graph_connector.insert_global_arcs(transfer_arcs, 1)
    graph_connector.insert_global_arcs(core_arcs, 1)
    
    log_info("Level 2 graph hierarchy - hubs: "  + dataset_name)
    """ add highlevel arcs to the original graph """
    core_graph = dict()
    update_graph(core_graph, core_arcs + transfer_arcs)
    node_list = [node for node in core_graph]
    _hub_nodes, highway_arcs = algorithm.graph_hubs(core_graph, node_list, node_list)
    del core_graph
    graph_connector.insert_global_arcs(highway_arcs, 2)
    
    log_info("Level 1 & 2 local graph hierarchy end: " + dataset_name)


def global_hierarchy(dataset_list = None):
    ''' Level 3 hierarchy on the global graph
            1. Build walk links for near stops
            2. Load all the high level nodes, arcs and these walk links
            3. Run hub algorithm again
    '''
    
    if dataset_list is None:
        results = execute_select("SELECT dataset_name FROM gtfs_dataset WHERE dataset_name <> 'gtfs'")
        dataset_list = [item[0] for item in results]
    
    log_info("Level 3 graph hierarchy - inter coupling")
    
    for k in range(1, len(dataset_list)):
        for dataset1, dataset2 in zip(dataset_list[:-k], dataset_list[k:]):
            transfer_arcs, overlapped = graph_coupling.inter_graph_transfers(dataset1, dataset2)
            if overlapped:
                graph_connector.insert_global_arcs(transfer_arcs, level = 1)
                ''' then we should find new hub nodes covering the overlapped graph '''
                pass
            else:
                graph_connector.insert_global_arcs(transfer_arcs, level = 2)
                ''' then we should find highway links from these new nodes of level 2 '''
                pass
            
            #TODO: following line is to be removed, its just temporary walking links for test 
            graph_connector.insert_global_arcs(transfer_arcs, 0)
    
    #TODO: now we only do walking links
    return
    
    log_info("Level 3 graph hierarchy - level 3 hubs")
    
    graph = graph_connector.load_highway_graph(level = 2)
    node_list = [node for node in graph]
    _hub_nodes, highway_arcs = algorithm.graph_hubs(graph, node_list, node_list)
    graph_connector.insert_global_arcs(highway_arcs, 3)
    
    log_info("Level 3 global graph hierarchy end")


if __name__ == '__main__':
    log_info("main: what wrong ???")

